Hard disk based storage traditionally has been used to store computer data. Hard disk capacity has increased dramatically over the years; however, hard disk performance in terms of Input/Output Operations per Second (hereafter “IOPS”) has scaled more slowly and has reached a saturation point. The terms “hard disk drive” and “hard disk” are used interchangeably herein to refer to computer-based non-volatile magnetic data storage.
Digital memories based on electronic circuitry perform faster than conventional hard disks. Thus, storing data in digital memory is an effective way to increase and improve upon the performance of hard disks. However, there are problems associated with conventional digital memory solutions. Traditionally, Dynamic Random Access Memory (DRAM) has been used to provide fast access to data. More recently, NAND Flash™ memory (hereafter “Flash” or “Flash chip”) has surpassed DRAM in terms of cost and capacity and is becoming a popular choice for high performance storage. Flash memory is typically implemented as solid state storage, such as a solid state drive (SSD), which is packaged similar to a hard disk and has a similar interface and programming model.
On a cost per gigabyte (GB) basis, Flash is more expensive than hard disks. Therefore, it is desirable to save costs by compressing data before storing it in Flash, such that the data may be saved using less Flash memory. This also has the advantage of reducing the amount of data that needs to be written to Flash, which improves performance.
However, the challenge in introducing compression in solid state storage is that compression and decompression engines must process data at very high rates to achieve performance rates similar to those of Flash-based memories. This poses a challenge because compression and decompression algorithms are compute-intensive (i.e., require a large number of computing operations). Conventional software-based approaches, running compression and decompression algorithms in a host processor, are unlikely to be able to keep up with the performance requirements. Also, there are performance limitations with conventional dedicated hardware for compression and decompression. For example, an SSD implementation can require many Flash chips in parallel to read and write data at very high rates. Some Flash chips, such as those compliant with the Open NAND Flash Interface (ONFI) 2.0 specification, can supply data at rates of approximately 166 megabytes (MB) per second. Further, it is not uncommon to operate 16 to 24 such Flash chips in parallel, which results in data rates as high as 4 GB/s, which is difficult to approximate using conventional compression and decompression solutions. It is desirable to achieve decompression at rates approaching 4 GB/s, which conventional software and hardware compression and decompression tools cannot achieve without incurring significant expense and complex architectures.
One conventional solution uses a lossless compression algorithm, such as Lempel-Ziv compression algorithms and variable length coding. A conventional architecture for performing such lossless compression can include a unit configured to implement Lempel-Ziv compression followed by another unit configured to implement variable length coding. Some Lempel-Ziv compression algorithm solutions include a hash module, a module for resolving collision chains, and a module for performing longest match searches. Some Lempel-Ziv compression algorithm solutions also include various units of RAM memory for storing hash data or collision chains data. Variable length coding following Lempel-Ziv compression is used conventionally to maintain superior compression ratios; however conventional compression and decompression solutions involving variable length coding cannot be scaled to achieve 4 GB/s.
Thus, what is needed is a solution for decompression of data at high speeds without the limitations of conventional techniques.